#include "util.h"
#include "common_sort.h"

/*
T(n) = 2 * T(n/2) + O(n)

==> O(nlogn)

*/

void MergeSort::sort(std::vector<int>& vec) {
	int sz = vec.size();
	if (!sz || sz == 1) {
		return;
	}

	mergeSort(vec, 0, sz - 1);
}

void MergeSort::merge(std::vector<int>& vec, int left, int mid, int right) {
	int lSz = mid - left + 1;
	int rSz = right - mid;
	
	std::vector<int> lvec(lSz);
	std::vector<int> rvec(rSz);

	for (int i = 0; i < lSz; ++i) {
		lvec[i] = vec[left + i];
	}

	for (int i = 0; i < rSz; ++i) {
		rvec[i] = vec[mid + 1 + i];
	}

	int lIndex = 0;
	int rIndex = 0;
	int index = left; // 注意这里要从left开始,不要从0开始
	while (lIndex < lSz && rIndex < rSz) {
		if (lvec[lIndex] <= rvec[rIndex]) {
			vec[index] = lvec[lIndex];
			lIndex++;
		} else {
			vec[index] = rvec[rIndex];
			rIndex++;
		}

		index++;
	}

	while (lIndex < lSz) {
		vec[index] = lvec[lIndex];
		lIndex++;
		index++;
	}

	while (rIndex < rSz) {
		vec[index] = rvec[rIndex];
		rIndex++;
		index++;
	}
}

void MergeSort::mergeSort(std::vector<int>& vec, int start, int end) {
	if (start >= end) {
		return;
	}

	int mid = start + (end - start) / 2;

	mergeSort(vec, start, mid);
	mergeSort(vec, mid + 1, end);
	merge(vec, start, mid, end);
}

